package com.zcmyth;

import java.util.Stack;

import com.zcmyth.tree.BinaryTree;

//Given a binary tree, find 2 leaf nodes say X and Y such that F(X,Y) is 
//maximum where F(X,Y) = sum of nodes in the path from root to X + sum of 
//nodes in the path from root to Y - sum of nodes in the common path from root
//to first common ancestor of the Nodes X and Y

public class NodeDistance {

  public static <T extends Comparable<T>> int distance(BinaryTree.Node<T> root, T node1, T node2) {
    Stack<BinaryTree.Node<T>> path1 = getPath(root, node1);
    Stack<BinaryTree.Node<T>> path2 = getPath(root, node2);
    int common = 0;
    for (; common < path1.size() && common < path2.size(); common++) {
      if (path1.get(common).getData().compareTo(path2.get(common).getData()) != 0) {
        break;
      }
    }
    common--;
    if(common < 0) {
      common = 0;
    }
    return path1.size() + path2.size() - common;
  }

  public static <T extends Comparable<T>> Stack<BinaryTree.Node<T>> getPath(
      BinaryTree.Node<T> root, T node) {
    Stack<BinaryTree.Node<T>> stack = new Stack<BinaryTree.Node<T>>();
    stack.add(root);
    while (!stack.isEmpty()) {
      BinaryTree.Node<T> top = stack.peek();
      if (top.getData().compareTo(node) == 0) {
        stack.pop();
        break;
      }
      if (top.getLeft() != null && !top.getLeft().isVisited()) {
        stack.push(top.getLeft());
      } else if (top.getRight() != null && !top.getRight().isVisited()) {
        stack.push(top.getRight());
      } else {
        top.setVisited(true);
        stack.pop();
      }
    }
    return stack;
  }
}
